//
// Created by weslywang on 2020/6/25.
//

#include "../common/common.h"

bool isAdjectFlag(int i, int k, vector<vector<char>> &board, char flag) {
    if (k - 1 >= 0 && board[i][k - 1] == flag || i - 1 >= 0 && board[i - 1][k] == flag ||
        k + 1 < board[0].size() && board[i][k + 1] == flag || i + 1 < board.size() && board[i + 1][k] == flag) {
        return true;
    }
    return false;
}

void colorFlag(int i, int k, vector<vector<char>> &board, char flag) {
    if (i >= 0 && i < board.size() && k >= 0 && k < board[0].size()) {
        board[i][k] = flag;
    }
    int w = k - 1;
    // 左侧染色
    if (w >= 0 && board[i][w] == 'O') {
        colorFlag(i, w, board, flag);
    }
    w = i - 1;
    // 上侧染色
    if (w >= 0 && board[w][k] == 'O') {
        colorFlag(w, k, board, flag);
    }
    w = k + 1;
    // 右侧染色
    if (w < board[0].size() && board[i][w] == 'O') {
        colorFlag(i, w, board, flag);
    }
    w = i + 1;
    // 下侧染色
    if (w < board.size() && board[w][k] == 'O') {
        colorFlag(w, k, board, flag);
    }
}

void solve(vector<vector<char>> &board) {
    if (board.size() <= 1) {
        return;
    }
    char flag = '*';
    int width = board[0].size(), height = board.size();
    int circle = 0;
    while (width - circle * 2 > 0 && height - circle * 2 > 0) {
        //上
        for (int i = circle, k = circle; k < width - circle; k++) {
            if (board[i][k] == 'O' && (circle == 0 || isAdjectFlag(i, k, board, flag))) {
                colorFlag(i, k, board, flag);
            }
        }
        // 右
        for (int i = circle, k = width - circle - 1; i < height - circle; i++) {
            if (board[i][k] == 'O' && (circle == 0 || isAdjectFlag(i, k, board, flag))) {
                colorFlag(i, k, board, flag);
            }
        }
        // 下
        for (int i = height - circle - 1, k = 0; k < width - circle; k++) {
            if (board[i][k] == 'O' && (circle == 0 || isAdjectFlag(i, k, board, flag))) {
                colorFlag(i, k, board, flag);
            }
        }
        // 左
        for (int i = circle, k = circle; i < height - circle; i++) {
            if (board[i][k] == 'O' && (circle == 0 || isAdjectFlag(i, k, board, flag))) {
                colorFlag(i, k, board, flag);
            }
        }

//        cout << "第" << circle << "圈" << endl;
//        Common common;
//        common.printCharList(board);
        circle++;
    }

    for (int i = 0; i < board.size(); i++) {
        for (int k = 0; k < board[0].size(); k++) {
            if (board[i][k] == flag) {
                board[i][k] = 'O';
            } else if (board[i][k] == 'O') {
                board[i][k] = 'X';
            }
        }
    }
}

int main() {
    struct timeval start;
    struct timeval end;
    unsigned long timer;

    Common common;
    int a[] = {1, 2, 3, 4, 5};

    vector<vector<char>> numList = common.loadCharData();
    gettimeofday(&start, NULL);
    common.printCharList(numList);
    solve(numList);
    cout << "**************" << endl;
    common.printCharList(numList);

    gettimeofday(&end, NULL);
    timer = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
    cout << timer / 1000 << "毫秒" << endl;
    return 0;
}